1. Field of the Invention
The present invention relates to the field of concurrent processing of operations in a computer system with specific application to vector processing computer systems.
2. Prior Art
In many known computer systems, multiple processors are utilized to execute instructions. In such systems, it is often desired to execute instructions from a single process in parallel or concurrently. For example, it may be desired to execute an instruction sequence such as: EQU LOAD R5, memory EQU ADD R3, R2, R1
on two separate processors, the first processor loading register 5 from memory and the second processor adding the contents of register 3 and register 2, giving register 1 as a result.
Parallel or concurrent processing of instructions is relatively simple when the instructions do not share common data. Such instructions may be said to be disjoint or independent.
However, it may be desired to execute an instruction sequence such as: EQU LOAD R1, memory EQU ADD R3, R2, R1
on two separate processors. In such an instruction sequence, the contents of register 1 after execution of the instructions may depend on the relative speed of processing the two instructions if the instructions are processed concurrently.
For example, consider two concurrent instructions issued at clock.sub.n and clock.sub.n+k (k&gt;0), both referencing a common cell A. If the first instruction produces a result needed by the second instruction, then the second instruction is said to have a chain dependency on the first. In such a case, the execution of the second instruction must be delayed until the first instruction completes its write of A. The completion of writing A may be termed "clearing" the conflict.
If both instructions write A, then a data "hazard" exist and the instructions must complete in the order issued. If the first instruction reads location A and the second instruction writes to location A, then a data "hazard" also exists and the actions must proceed in time such that the read of A by the first instruction proceeds the write of A by the second instruction. These data conflicts are summarized in Table I below:
TABLE I ______________________________________ CHAINING AND HAZARD DEFINITION LATER ACTION FIRST READ WRITE ACTION A A ______________________________________ READ NO DATA A CONFLICT HAZARD WRITE CHAINING DATA A CONFLICT HAZARD ______________________________________
A number of methods and apparatus for solving such a concurrency problem are known in the art. For example, some programming languages allow for the programmer to code instructions to avoid data conflict problems posed by concurrent execution of instructions. An example of such a programming language is Concurrent SP/k (CSP/k), which is the SP/k subset of PL/I, extended with concurrency constructs. In CSP/k, the constructs are called monitors and are implemented around critical pieces of code. An example of CSP/k compiler that runs on an IBM system 360/370 was developed by the University of Toronto, Toronto, Ontario, Canada.
A number of other methods including use of specialized circuitry and hardware and software semaphores are known for implementing concurrent and parallel processings of instructions.
Processing of concurrent instructions is further complicated in a computer system having multiple processors in which the processor organization is a pipeline machine. With reference to FIG. 1, pipeline machines generally comprise one or more central processor units 101 having a plurality of separate units to execute each step of an instruction. For example, an instruction fetch unit 102 may fetch an instruction to be executed. An instruction analyzer unit 103 may decode the fetched instruction and the instruction fetch unit 102 may fetch a second instruction. An address calculation unit 104 determines if the initial instruction needs data from memory and the address of such data while the instruction analyzer 103 is decoding the second instruction and the instruction fetch unit is fetching a third instruction. A data fetch unit 105 may then fetch data from memory for the first instruction and an instruction execution unit 106 will subsequently execute the instruction. A data store unit 107 may then store a result in memory. Each instruction follows through each step down the pipeline.
In a computer system utilizing pipeline machines and concurrent or parallel processing it is important to examine data affected by each stage of the pipeline when determining if data conflicts exist.
Therefore, it is desired to develop a method and apparatus for determining whether data conflicts exist and for throttling execution of instructions where such conflicts exist in a computer system utilizing concurrent and parallel processing.
It is further desired to develop a method and apparatus for detecting data conflicts and for throttling execution of instructions where data conflicts exist in a computer system utilizing a plurality of processors having a pipeline architecture.